package bintree.nowcoder;

import java.util.Scanner;
/**
 * ACM 模式编程
 */

//节点类定义
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }

}

public class Main {
    public static int index = 0;//表示当前读取字符串的位置
    public static void main(String[] args) {
        Scanner sancc = new Scanner(System.in);
        //因为是多组测试，所以while。还需要判断是否还有该类型的输入
        while(sancc.hasNextLine()){
            //读取一串字符串
            String str = sancc.nextLine();
            //设计一个方法，根据这个前序遍历字符串创建二叉树
            TreeNode root = preOrderBuild(str);
            //再设计一个方法，根据这个树根节点中序遍历输出。
            inOrder(root);
            System.out.println();//打印玩一次就自动换行

            //事情都做完后让index归零，方便下次循环操作
            index = 0;
        }

    }

    /**
     * 按照中序遍历的方式遍历二叉树，并打印节点。
     */
    private static void inOrder(TreeNode root) {
        if(root == null){
            return;
        }
        //左 根 右
        //先递归左子树
        inOrder(root.left);
        //再打印根
        System.out.println(root.val + " ");
        //最后递归访问右子树
        inOrder(root.right);
    }

    /**
     *传入一个字符串str，就能按照前序遍历的方式还原为二叉树，返回根节点。
     */
    private static TreeNode preOrderBuild(String str) {
        //读取一个字符
        char cur = str.charAt(index);

        if(cur == '#'){
            //空树，无需创造节点
            return null;
        }
        TreeNode root = new TreeNode(cur);//创建一个节点值
        index ++;
        root.left = preOrderBuild(str);
        index ++;
        root.right = preOrderBuild(str);

        return root;
    }

}
